#!/usr/bin/python
#-*- coding:utf-8 -*-
# Description:  华容道问题求解.
#               8代表空格，从0开始（一般游戏从1开始）
#        breadth first search
#        
#  
################################################################
import numpy as np
from pprint import pprint
from collections import deque, namedtuple
import sys
sys.setrecursionlimit(100000)

class square(object):
    '华容道方格'
    def __init__(self, v = None):
        self.previous = None
        if isinstance(v, np.ndarray):
            self.v = v
        else:
            self.v = np.arange(9, dtype=int)

    def shuffle(self):
        np.random.shuffle(self.v)
            
    def label(self):
        '唯一数字标识'
        return reduce(lambda x, y: x*9 + y, self.v)

    def ind(self):
        return np.where(self.v == 8)[0][0]

    def up(self):
        i = self.ind()
        if i > 2 :
            t = self.v.copy()
            t[i], t[i-3] = self.v[i-3], 8
            return square(t)
        else :
            return None

    def down(self):
        i = self.ind()
        if i < 6 :
            t = self.v.copy()
            t[i], t[i+3] = self.v[i+3], 8
            return square(t)
        else :
            return None

    def left(self):
        i = self.ind()
        if i % 3 > 0 :
            t = self.v.copy()
            t[i], t[i-1] = self.v[i-1], 8
            return square(t)
        else :
            return None

    def right(self):
        i = self.ind()
        if i % 3 < 2 :
            t = self.v.copy()
            t[i], t[i+1] = self.v[i+1], 8
            return square(t)
        else :
            return None

        
    def __str__(self):
        return str(self.v.reshape(3,3))

direction = [ 'up', 'down', 'left', 'right']

path = []

target = 6053444
dbg_num = 0
queue = deque()
used = {}
def bfs(start):
    'start: 起始方格状态'
    found = False
    queue.append(start)
    while queue:
        n = queue.popleft()
        label = n.label()
        used[label] = n
        if label == target:
            found = True
            break
        for d in direction:
            if   d == 'up':    nxt = n.up()
            elif d == 'down':  nxt = n.down()
            elif d == 'left':  nxt = n.left()
            elif d == 'right': nxt = n.right()
            if nxt != None and not used.has_key(nxt.label()):
                nxt.previous = label
                queue.append(nxt)
    return found

def output(target):
    s = target
    path = []
    while s:
        path.append(used[s])
        s = used[s].previous
    for i, p in enumerate(reversed(path)):
        print "step = ", i
        print p
    return

if __name__ == '__main__':
    t = np.array([0,1,2,3,8,4,6,7,5], dtype=int)
    start = square(t)
    start.shuffle()
    if bfs(start):
        print "==========Got it:"
        output(target)
    else :
        print start
        print "Can't finished!"
